package 二叉搜索树的最近公共祖先;

/**
 * @author AirMan
 * @version 1.0
 * @description
 * @date 2025/4/7 10:09
 */
public class Solution2 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 迭代法
        // 把握住二叉搜索树的特性（左 < 中 < 右），我们不需要用栈去记录根节点，因为我们根本不需要去处理根节点
        // 只需要查看当前节点是不是位于两节点的区间内，只要出现该情况那么就返回root
        if (p.val > q.val) {
            TreeNode temp = p;
            p = q;
            q = temp;
        }
        while (true) {
            if (root.val < p.val) {
                root = root.right;
            } else if (root.val > q.val) {
                root = root.left;
            } else {
                return root;
            }
        }
    }
}
